package resilienceManager.qmul.gemom;

import inl.resilienceManager.qmul.gemom.VarianceCalculation;

import java.util.Collections;
import java.util.LinkedList;
import java.util.Vector;

import javax.swing.tree.DefaultMutableTreeNode;
import javax.swing.tree.TreeNode;

/**
 * 
 * A star algorithm , which used for the optimizaiton
 * 
 * COPYRIGHT DISCLAIMER
 * Synopsis: All the source codes presented in this document are intellectual
 * properties of Queen Mary, University of London.
 * 
 * @year 2010
 * @author Peng Jiang, John Bigham, Jiayi Wu, Jinfu Wang------------QMUL
 * @version 1.0 
 */



public class starSearch {
	// the list of the items
	private static NSitem[] itemlist ;

	// the list of the bidders
	private static Gbroker[] bidders;

	// the ID of Broken gbroker
	private int bgID;

	// the value list of the items
	private int[] valuelist;

	// the default root of the bid tree
	bidNode rootNode=null;


	// the vector used to store the node in one level
	private static Vector<bidNode> nodelist = new Vector<bidNode>();;

	// the vector used to store the node value ( f=g+h)
	private static Vector<Double> fList = new Vector<Double>();;


	// the power set of the items
	private static  LinkedList<LinkedList<Integer>> AllSet;

	// the linkedlist build by all the items;
	private static LinkedList<Integer> AllItems;

	// the vector for saving the leaf of the tree
	private static Vector<bidNode> leafList = new Vector<bidNode>();

	// the risk value for the path
	private static Vector<Double> riskList = new Vector<Double>();

	// the minimum risk of the solution
	public double risk_sl;



	/**
	 * constractor with the itemlist and gbroker list
	 * 
	 * gbroker list has the current 
	 * 
	 * */
	public starSearch(NSitem[] ilist, Gbroker[] glist, int id)
	{

		this.itemlist=ilist;

		this.bidders=glist;

		this.bgID = id;

		this.valuelist=new int[this.itemlist.length];

		AllItems = new LinkedList<Integer>();

		for(int i=0; i< itemlist.length;i++)
		{
			this.valuelist[i]=itemlist[i].nslist.size();
			AllItems.add(i);

		}



	}

	/**
	 * 
	 * get the bid tree root
	 * */

	public DefaultMutableTreeNode getBidTree()
	{

		return (DefaultMutableTreeNode)rootNode;
	}


	/**
	 * the main method to buid the tree with A star algorithm
	 * 
	 * 
	 * **/

	public void buildTree()
	{
		LinkedList<Integer> va=new LinkedList<Integer>(); 

		for(int i=0; i<itemlist.length; i++)
		{
			va.add((Integer)itemlist[i].getID());
		}

		AllSet= powSet(va);

		rootNode= new bidNode("A*");

		bidNode currentNode=rootNode;

		LinkedList<Integer> bidList= new LinkedList<Integer>();


		LinkedList<LinkedList<Integer>> avSet=(LinkedList<LinkedList<Integer>>) AllSet.clone();

		while(true)
		{

			for(int i=0; i<avSet.size(); i++)
			{

				int level=currentNode.getLevel();
				Gbroker currentBid=bidders[level];

				LinkedList<Integer> ta=avSet.get(i);

				if(ta.size()>0)
				{
					if(currentBid.acceptAll(getValueOflist(ta)))
					{
						String name="";
						for(int j=0; j<ta.size(); j++)
						{
							int id=ta.get(j)+1;
							if(j!=(ta.size()-1))
								name=name+id+"-";
							else
								name=name+id;
						}

						bidNode newNode= new bidNode(name,ta);

						currentNode.add(newNode);


						nodelist.add(newNode);

						double fvalue=allValue(newNode,level);

						fList.add(fvalue);


						if(newNode.getLevel()==bidders.length)
						{
							leafList.add(newNode);
							riskList.add(getRiskvalue(newNode));

						}


					}
				}
			}


			int optimalID=sortList(fList);

			currentNode=nodelist.get(optimalID);

			LinkedList<Integer> uplist=getItemAbove(currentNode);

			//if(uplist.size()==AllItems.size())
			if(leafList.size()>(bidders.length*100))
				return;


			while(currentNode.getLevel()>(bidders.length-1))
			{

				nodelist.remove(optimalID);
				fList.remove(optimalID);

				if(fList.size()==0)
					return;

				optimalID=sortList(fList);

				currentNode=nodelist.get(optimalID);



			}
			uplist=getItemAbove(currentNode);


			avSet=findPoSet(AllSet, uplist);	

			nodelist.remove(optimalID);
			fList.remove(optimalID);

			if(fList.size()==0)
				return;


		}


	}

	public DefaultMutableTreeNode SearchTree(){

		DefaultMutableTreeNode root= new DefaultMutableTreeNode("A*");

		DefaultMutableTreeNode current = null;
		double minRisk=1000000;

		int bidID=0;
		for(int i=0; i< riskList.size(); i++)
		{
			double t=riskList.get(i);
			if((t>0)&&(t<minRisk))
			{
				minRisk=t;
				bidID=i;
			}
		}

		this.risk_sl=minRisk;

		System.out.println("Star Risk="+minRisk);

		bidNode winBid=leafList.get(bidID);

		TreeNode[] nodelist=winBid.getPath();


		for(int i=0; i<nodelist.length; i++)
		{
			if(nodelist[i].toString().equals("A*"))
			{
				// do nothing
				current=root;
				continue;
			}
			else
			{

				DefaultMutableTreeNode addNode= new DefaultMutableTreeNode(nodelist[i].toString());
				current.add(addNode);

				current=addNode;

			}
		}

		return root;

	}


	/**
	 * 
	 * sort the f value list 
	 * 
	 * get the smallest value 
	 * 
	 * */

	private int sortList(Vector<Double> list)
	{

		int id=0;

		double min=list.get(id);

		for(int i=1; i<list.size(); i++)
		{
			if(min>list.get(i))
			{
				id=i;
				min=list.get(id);
			}
		}

		return id;
	}

	/**
	 * the f function in the A star algorithm
	 * 
	 * get the sum of g and h
	 * 
	 * */
	private double allValue(bidNode node, int level)
	{
		double fvalue=0;

		double gvalue=0;

		double hvalue=0;


		gvalue=bidders[level].getRisk(node.getNodeVariance(itemlist),node.getNodevalue(itemlist));

		bidNode p=(bidNode) node.getParent();

		while(!p.toString().equals("A*"))
		{

			int l=p.getLevel();
			double t=bidders[l].getRisk(p.getNodeVariance(itemlist),p.getNodevalue(itemlist));

			gvalue=gvalue+t;

			p=(bidNode)p.getParent();

		}

		hvalue=estimatedValue(node, level);

		fvalue=gvalue+hvalue;

		return fvalue;


	}




	/**
	 * the method to calaculte the estimated value fromt this node
	 * 
	 * the h function in the A star algorithm
	 * 
	 * **/
	private double estimatedValue(bidNode node, int level)
	{
		double h=0;

		double addH=0;

		// get the maximum value of the item combination
		LinkedList<Integer> m=findMin(node);

		LinkedList<Integer> t=restItem(node);


		// get all the estimated from this level

		for(int i=level+1; i<bidders.length; i++)
		{
			//addH=bidders[level].getRisk(getValueOflist(m))+bidders[level].getRisk(getValueOflist(t));
			NSitem[] alist= new NSitem[m.size()];
			for(int j=0; j<m.size(); j++)
			{
				alist[j]= itemlist[m.get(j).intValue()];
			}
			
			
			addH=bidders[i].getRisk(getValueOflist(m));
			//addH=bidders[level].getRisk(getValueOflist(t));
			h=h+addH;
		}


		return h;
	}


	/**
	 * 
	 * find the rest of item 
	 * */

	private LinkedList<Integer> findRest(bidNode node)
	{
		LinkedList<Integer> m = null;


		m=(LinkedList<Integer>) AllItems.clone();


		LinkedList<Integer> t=getItemAbove(node);

		for (int i=0 ; i< t.size(); i++)
		{
			int remove=t.get(i);

			m.remove((Integer) remove);
		}

		int id=0;
		int min=itemlist[m.get(id)].nslist.size();

		for(int i=1; i<m.size(); i++)
		{
			if(min>itemlist[m.get(i)].nslist.size())
			{
				id=i;
				min=itemlist[m.get(i)].nslist.size();
			}
		}

		m.clear();
		m.add(id);

		return m;
	}



	/**
	 * 
	 * get the maximum value from the all the power set
	 * 
	 * except the input item
	 * 
	 * return the id of the item combinaiton
	 * 
	 * */
	private LinkedList<Integer> findMin(bidNode node)
	{
		LinkedList<Integer> m = null;
		// delete already used 

		LinkedList<Integer> tall=getItemAbove(node);

		LinkedList<LinkedList<Integer>> t=findPoSet(AllSet, tall);	
		// find the maximum value of the combination

		double va=0;

		int id=0;

		for(int i=0; i<t.size(); i++)
		{

			if(t.get(i).size()>0)
			{
				double tempv=getValueOflist(t.get(i));
				if(tempv>va)
				{
					va=tempv;
					id=i;
				}
			}

		}

		m=t.get(id);

		return m;
	}


	private static double getRiskvalue(bidNode leaf)
	{
		double risk = 0;

		Vector<Integer> totalItem=new Vector<Integer>();

		TreeNode[] nodelist=leaf.getPath();

		for(int i=0; i<nodelist.length; i++)
		{
			if(nodelist[i].toString().equals("A*"))
			{
				// nothing doing
				continue;
			}
			else
			{
				bidNode temp=(bidNode) nodelist[i];

				for(int j=0; j<temp.getBidItem().size();j++)
				{
					totalItem.add(temp.getBidItem().get(j));
				}

				risk=risk+ bidders[i-1].getRisk(temp.getNodevalue(itemlist));

			}
		}


		if(totalItem.size()==AllItems.size())
		{
			return risk;
		}
		else
		{
			risk=-1;
			return risk;
		}

	}


	/**
	 * 
	 * get the rest item list
	 * 
	 * @param bidNode: current node
	 * @return LinkedList: the list of rest items
	 * 
	 * **/
	private LinkedList<Integer> restItem(bidNode node)
	{

		LinkedList<Integer> rest=(LinkedList<Integer>) AllItems.clone();

		TreeNode[] path=node.getPath();

		for(int i=0; i<path.length; i++)
		{

			bidNode tnode=(bidNode)path[i];


			if(tnode.toString().equals("A*"))
			{
				// nothing doing
				continue;
			}
			else
			{

				LinkedList<Integer> t=tnode.getBidItem();

				for (int j=0 ; j< t.size(); j++)
				{
					int remove=t.get(j);

					if(rest.contains((Integer)remove))
						rest.remove((Integer) remove);
				}
			}

		}

		return rest;
	}

	private static LinkedList<LinkedList<Integer>> findPoSet(LinkedList<LinkedList<Integer>> PoSet, LinkedList<Integer> used)
	{

		LinkedList<LinkedList<Integer>> tem=(LinkedList<LinkedList<Integer>>) PoSet.clone();


		for(int i=0; i< used.size(); i++)
		{
			int itemID=used.get(i);
			tem=exceptItem(tem, itemID);

		}


		return tem;
	}


	private static LinkedList<LinkedList<Integer>> exceptItem( LinkedList<LinkedList<Integer>> AL, int itemID)
	{

		LinkedList<LinkedList<Integer>> tem=(LinkedList<LinkedList<Integer>>) AL.clone();
		LinkedList<LinkedList<Integer>> deID=new LinkedList<LinkedList<Integer>>();


		for(int i=0; i<tem.size(); i++)
		{
			LinkedList<Integer> temList=tem.get(i);

			if(temList.contains((Integer)itemID))
			{
				deID.add(temList);
			}
		}

		tem.removeAll(deID);


		return tem;


	}

	/**
	 * find already used list
	 * 
	 * return already used the item list
	 * */
	private static LinkedList<Integer> getItemAbove(bidNode current)
	{
		LinkedList<Integer> above = (LinkedList<Integer>) current.getBidItem().clone() ;

		bidNode currentNode=current;

		while(!currentNode.toString().equals("A*"))
		{
			bidNode pNode=(bidNode) currentNode.getParent();

			if(!pNode.toString().equals("A*"))
			{
				for(int i=0; i<pNode.getBidItem().size(); i++)
				{
					if(!above.contains(pNode.getBidItem().get(i)))
						above.add(pNode.getBidItem().get(i));
				}
				currentNode=pNode;
			}
			else
				return above;

		}

		return above;
	}
	/**
	 * 
	 * the g function in A star algorithm
	 * 
	 * 
	 * */

	private static int getValueOflist(LinkedList<Integer> la)
	{
		int value=0;


		for(int i=0; i<la.size(); i++)
		{
			value=value+itemlist[la.get(i)].nslist.size();
		}

		return value;

	}
	/**
	 * The main method to find all the sub set based on the linkedlist A
	 * 
	 * recursive algorithm
	 * */

	private static LinkedList<LinkedList<Integer>>  powSet(LinkedList<Integer> A)
	{	
		LinkedList<LinkedList<Integer>> ans= new LinkedList<LinkedList<Integer>> ();	
		if(A.size() == 1){//if there's only one element, we know the answer	

			ans.add(new LinkedList<Integer>());//empty set		

			LinkedList<Integer> temp= new LinkedList<Integer>();		

			temp.add(A.get(0));//and the only element in the original set	

			ans.add(temp);	

		}else{

			int first= A.remove(0);//save the first element		

			LinkedList<LinkedList<Integer>> partial= powSet(A);//recursion call		

			for(LinkedList<Integer> subset: partial) //for each set in the partial set
			{			
				//add it to the answer
				ans.add(subset);

				LinkedList<Integer> temp= new LinkedList<Integer>(subset);			
				//add the saved element to it	
				temp.add(first);
				//sort that set	
				Collections.sort(temp);	
				//add the new set to the answer
				ans.add(temp);		
			}	
		}	
		return ans;
	}


}
